During graphics processing, a computer is commonly used to display three-dimensional representations of an object on a two-dimensional display screen. In a typical graphics computer, an object to be rendered is divided into a plurality of graphics primitives. The graphics primitives are basic components of a graphics picture and may be defined by geometry such as a point, line, vector, or polygon, such as a triangle.
To produce an image for the two-dimensional display screen, the following two steps are typically performed, as well as others not described in detail here.                Eye-view visibility: For each pixel on the two-dimensional display screen, the computer determines which primitive is visible (i.e. front-most) at that pixel. The computer also determines the exact point on that primitive that is visible at the pixel.        Light visibility (shadow computation): For each surface point that was determined to be visible by the first step, the computer determines whether the surface point is visible from the light source, indicating whether or not the surface point is in shadow. If there is more than one light source, this step is repeated for each light source.        
These two tasks and others can be considered to be specific cases of the problem of determining which surfaces are visible (i.e. intersected first) along a specific a set of rays.
The prior art consists of a wide variety of approaches for performing visibility tests, including:                Ray tracing: Turner Whitted, An Improved Illumination Model for Shaded Display, Communications of the ACM, vol. 23, no. 6, June 1980, pp. 343-349.        Classical Z-buffer: Ed Catmull, A Subdivision Algorithm for Computer Display of Curved Surfaces, Ph.D. Dissertation, University of Utah, 1974.        Shadow mapping (classical Z-buffer used for light viewpoint): Lance Williams, Casting Curved Shadows on Curved Surfaces, Computer Graphics (SIGGRAPH 1978), vol. 12, no. 3, August 1978, pp. 270-274.        Shadow volumes: Franklin Crow, Shadow Algorithms for Computer Graphics, Computer Graphics (SIGGRAPH 1977), vol. 11, no. 2, July 1977.        -And-        Morgan McGuire and John F. Hughes and Kevin Egan and Mark Kilgard and Cass Everitt. Fast, Practical, and Robust Shadows. Brown University Technical Report CS03-19, October 2003.        
All publications, patent applications, patents, and other references mentioned herein are incorporated by reference in their entirety.
The ray tracing approach is highly general, but it is computationally expensive. The ray tracing approach has the additional disadvantage that the rendering system maintains a large spatially sorted data structure containing the graphics primitives. For these reasons, the ray tracing approach has not been widely used by interactive rendering systems.
The conventional Z-buffer approach is the approach most commonly used in real-time rendering systems. However, it can only evaluate a restricted set of visibility queries: those in which all rays share a common origin and whose directions are regularly spaced. This restriction is equivalent to stating that an image generated using this technique must have its sample points located in a regular pattern such as a grid, as shown in FIG. 1. When the Z-buffer visibility approach is used for the purpose of computing shadows (i.e. shadow mapping), it produces visually objectionable errors such as those shown in FIG. 3.
The shadow volume technique was developed to avoid the objectionable errors of shadow mapping. Although the shadow volume technique has been used occasionally in commercial systems, it is widely considered to require excessive computational resources and to be particularly difficult to integrate into a complete and flexible image generation system.
Therefore, a need exists for a method and apparatus for computing visibility that is more efficient than ray tracing and shadow volumes; that produces fewer visual errors than shadow mapping; that is simpler to integrate into a complete system than shadow volumes; and that supports a more flexible set of visibility queries than the conventional Z-buffer. More specifically, a need exists for a method and apparatus for computing visibility that runs at real-time frame rates and whose programming interface is similar to that of the conventional Z-buffer, but that allows visibility to be computed for an irregularly arranged set of points on the image plane as shown in FIG. 2.